Universal Composability
Resources
Ran Canetti
Detailed presentation of UC, its shortcomings, and ways around it
25 episodes / 4 hours
Tutorial style papers
Christian Badertscher, Ueli Maurer, Daniel Tschudi and Vassilis Zikas
Questions on Cryptography StackExchange
Preliminaries
Model of protocol execution: A protocol execution consists of a set of interacting computing elements modelled as interactice Turing machines (ITMs).
Adversary: An adversary is another ITM with the following properties:
Controls a subset of parties
Control over scheduling and delivering messages (subject to synchrony property)
Inputs: Parties are interacting on a given set of inputs
Global outputs: Each party eventually generates a local output. The global output is the concatenation of all parties and the adversary local output.
Ideal process: In the ideal process for evaluating some function f, all parties ideally hand their inputs to an incorruptible trusted party, who computes the function values and hands them to the parties as specified. Here the adversary is limited to interacting with the trusted party in the name of the corrupted parties. Protocol π securely evaluates a function f if for any adversary A (that interacts with the protocol) there exists an ideal-process adversary S such that, for any set of inputs to the parties, the global output of running π with A is indistinguishable from the global output of the ideal process for f with adversary S.
This definition does not hold for the concurrent execution of processes!
In UC, the adversary can freely interact with the environment (information exchange after messages or generated output)
https://gyazo.com/1eed9e14ed9c941e887c9226ad5ebf58
UC model
Idea: The security of a system is reflected only in its effects on the rest of the external environment.
Design an ideal functionality F with a certain specification.
System P UC-realizes F if for any environment E the execution cannot determine if it is on the ideal functionality with a simulator or the sytem.
Construction of UC
Model: $ (\mathcal{E}, \mathcal{A}, \pi_1, .., \pi_n) (Environment, Adversary, protocol instance 1 to n)
Execution: $ \mathrm{EXEC}_{\pi, \mathcal{A}, \mathcal{E}} represents the esemble of distributions form the input of the environment from {0,1}
Protocol execution
https://gyazo.com/3c0533e56b519a253fffa09baae881b4
Ideal protocol
https://gyazo.com/d44972b05dd3b8744f76ac9fd933203a
Definition (protocol emulation, informal statement): Protocol $ \pi UC-emulates (ideal) protocol $ \phi if for any adversary $ \mathcal{A} there exists an adversary $ \mathcal{S} such that, for any environment $ \mathcal{E} the ensembles $ \mathrm{EXEC}_{\pi, \mathcal{A}, \mathcal{E}} and $ \mathrm{EXEC}_{\phi, \mathcal{S}, \mathcal{E}} are indistinguishable. That is, on any input, the probability that $ \mathcal{E} outputs 1 after interacting with $ \mathcal{A} and parties running $ \pidiffers by at most a negligible amount from the probability that $ \mathcal{E}outputs 1 after interacting with $ \mathcal{S} and $ \phi.
F-hybrid protocols
Parties in an arbirtrary protocol make calls to an ideal functionality F.
There are multiple instances of F and parties can make calls to those instances.
The instances of F run at the same time without any global coordination.
The protocol needs to distinguish the instances of F (UC only provides the session identifiers)
Approach of UC
Define the ideal functionalities of the ledger
Define the protocol(s) that implement the ledger
Define the simulators that interact with the environment
Prove that ideal functionality and the protocol with the simulators are indistinguishable
Prove chain specific properties (common prefix, chain growth, chain quality etc.) from the ideal ledger functionality later
Protocols
UC allows to handle sub-protocols
Prove that sub-protocol is secure and than use composition to prove that the resulting protocol is also secure
Interactice Turing Machine/Instances
Basic model of "units" or processes in UC are Interactive Turing machines with a range of tapes
Assumption: each ITM is able to complete their computations at polynomial time
An instance of an ITM is called an Interatice Turing machine Instance (ITI)
Extensions
Ran Cohen, Sandro Coretti, Juan Garay and Vassilis Zikas
Define secure multi-party computation (MPC) with probabilistic termination in the UC framework and prove a universal composition theorem for probabilistic-termination protocols
Kevin Liao (University of Illinois), Matthew A. Hammer (DFINITY) and Andrew Miller (University of Illinois)
Juan Garay (AT&T Labs), Jonathan Katz (University of Maryland), Ueli Maurer (ETH Zurich) , Bj¨orn Tackmann (ETH Zurich) and Vassilis Zikas (UCLA)